package demo1;
import java.util.*;
  class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class Solution {
    //1.剑指 Offer 06. 从尾到头打印链表
    public int[] reversePrint(ListNode head) {
        ListNode cur = head;
        int len = 0;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        cur = head;
        //计算链表长度
        int[] arr = new int[len];
        int end = len - 1;//数组指针
        for(int i = 0; i < len; i++) {
            arr[end--] = cur.val;
            cur = cur.next;
        }
        return arr;
    }
    //剑指 Offer 06. 从尾到头打印链表(辅助栈)
/*    public int[] reversePrint(ListNode head) {
        //辅助栈
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        int len = 0;//记录长度
        while(cur != null) {
            len++;
            stack.push(cur.val);
            cur = cur.next;
        }
        int[] arr = new int[len];
        int arrIndex = 0;//arr的下标
        while(!stack.empty()) {
            arr[arrIndex++] = stack.pop();
        }
        return arr;
    }*/
    //2.剑指 Offer 18. 删除链表的节点
    public ListNode deleteNode(ListNode head, int val) {
        if(head == null) {
            return null;
        }
        ListNode cur = head;
        ListNode prev = cur;//永远指向cur的上一个结点
        while(cur != null) {
            //要删除的位置在头节点
            if(head.val == val) {
                head = head.next;
                return head;
                //要删除的位置在结尾
            }else if(cur.next == null && cur.val == val) {
                prev.next = null;
                return head;
                //要删除的位置在中间
            }else if(cur.val == val){
                prev.next = cur.next;
                //cur = cur.next;//这一步对于这道题来说可以没有
                return head;
            }
            prev = cur;
            cur = cur.next;
        }
        //结点不存在
        return null;
    }
    //剑指 Offer 22. 链表中倒数第k个节点
/*    public ListNode getKthFromEnd(ListNode head, int k) {
        //计算链表的长度
        ListNode cur = head;
        int len = 0;
        while(cur != null) {
            len++;
            cur = cur.next;
        }
        cur = head;
        while(len - k > 0) {
            cur = cur.next;
            k++;
        }
        return cur;
    }*/
    //3.剑指 Offer 22. 链表中倒数第k个节点(快慢指针)
    public ListNode getKthFromEnd(ListNode head, int k) {
        //快慢指针法
        ListNode fast = head;
        while(fast != null) {
            //先让快指针走k步，再让慢指针和快指针同时走，快指针到边界的时候就结束了
            if(k > 0) {
                fast = fast.next;
                k--;
            }else {
                fast = fast.next;
                head = head.next;
            }
        }
        return head;
    }
    //4.剑指 Offer 24. 反转链表(辅助栈)
/*    public ListNode reverseList(ListNode head) {
        //辅助栈
        Stack<Integer> stack = new Stack<>();
        ListNode cur = head;
        while(cur != null) {
            stack.push(cur.val);
            cur = cur.next;
        }
        cur = head;
        while(cur != null) {
            cur.val = stack.pop();
            cur = cur.next;
        }
        return head;
    }*/
    //剑指 Offer 24. 反转链表(双指针法)
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        //原链表上修改(修改地址法)
        ListNode cur = head;
        ListNode prev = null;//开头可以充当虚拟结点，后面可以充当cur结点的上一个结点
        while(cur != null) {
            ListNode tmp = cur.next;//暂存下一个结点的地址
            cur.next = prev;
            prev = cur;
            cur = tmp;
        }
        return prev;
    }

    //5.剑指 Offer 25. 合并两个排序的链表(新链表法)
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if(l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        if(l1 == null && l2 == null) {
            return null;
        }
        //虚拟头节点
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                ListNode p = new ListNode(l1.val);
                cur.next = p;
                cur = cur.next;
                l1 = l1.next;
            }else {
                ListNode p = new ListNode(l2.val);
                cur.next = p;
                cur = cur.next;
                l2 = l2.next;
            }
        }
        //还剩下没接完的
        if(l1 != null) {
            cur.next = l1;
        }
        if(l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }
    //6.剑指 Offer 35. 复杂链表的复制(map映射法)
/*    public Node copyRandomList(Node head) {
        if(head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();//记录两个链表每个结点的映射关系
        Node retHead = new Node(head.val);
        map.put(head, retHead);
        Node cur1 = head.next;
        Node cur2 = retHead;
        while(cur1 != null) {
            Node node = new Node(cur1.val);
            cur2.next = node;
            cur2 = cur2.next;
            map.put(cur1, cur2);
            cur1 = cur1.next;
        }
        //复制random
        cur1 = head;
        cur2 = retHead;
        while(cur1 != null) {
            cur2.random = map.get(cur1.random);
            cur1 = cur1.next;
            cur2 = cur2.next;
        }
        return retHead;
    }*/

    //7.剑指 Offer 52. 两个链表的第一个公共节点(快慢指针)
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //先计算出两个链表的长度
        ListNode cur1 = headA;
        ListNode cur2 = headB;
        int len1 = 0;
        int len2 = 0;
        while(cur1 != null) {
            len1++;
            cur1 = cur1.next;
        }
        while(cur2 != null) {
            len2++;
            cur2 = cur2.next;
        }
        cur1 = headA;
        cur2 = headB;
        //求出长度差dif后，让长的链表先走dif后，两个cur在一起跑
        if(len1 > len2) {
            int dif = len1 - len2;
            //长的先走差值步
            while(dif > 0) {
                cur1 = cur1.next;
                dif--;
            }
            //两个一起走，比较结点地址，若相同则说明这是公共结点
            while(cur1 != null && cur2 != null && cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            if(cur1 == null || cur2 == null) {
                return null;
            }
            return cur1;
        }else{
            int dif = len2 - len1;
            //长的先走差值步
            while(dif > 0) {
                cur2 = cur2.next;
                dif--;
            }
            //两个一起走，比较结点地址，若相同则说明这是公共结点
            while(cur1 != null && cur2 != null && cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            if(cur1 == null || cur2 == null) {
                return null;
            }
            return cur1;
        }
    }
    //8.两数相加(模拟进位)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int ans = 0;//表示进位
        int sum = 0;//表示每一位的和
        ListNode head = new ListNode(0);//虚拟头指针
        ListNode cur = head;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            sum = x + y + ans;
            ans = sum / 10;
            ListNode node = new ListNode(sum % 10);
            cur.next = node;
            cur = cur.next;
            if(l1 != null) {
                l1 = l1.next;
            }
            if(l2 != null) {
                l2 = l2.next;
            }
        }
        if(ans != 0) {
            ListNode node = new ListNode(ans);
            cur.next = node;
        }
        return head.next;
    }
    //9.删除链表的倒数第 N 个结点(进阶:快慢指针依次遍历)
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //快慢指针法
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;
        //让快指针先走n步
        while(n > 0) {
            fast = fast.next;
            n--;
        }
        //快慢指针一起走
        while(fast != null) {
            fast = fast.next;
            prev = slow;
            slow = slow.next;
        }
        //删除慢指针指向的结点即可
        if(slow == head) {
            head = head.next;
        }else {
            prev.next = slow.next;
        }
        return head;
    }
    //10.两两交换链表中的节点
    public ListNode swapPairs(ListNode head) {
        ListNode ret = new ListNode(0);
        ret.next = head;
        ListNode prev = ret;
        while(prev.next != null && prev.next.next != null) {
            ListNode start = prev.next;
            ListNode end = prev.next.next;
            prev.next = end;
            start.next = end.next;
            end.next = start;
            prev = start;
        }
        return ret.next;
    }
}
